let array = [0,2,23,33,32,31,51,62,33,37,21,10,0]
function mpSort(arr) {
  const length = arr.length
  for (let i = 0; i < length-1; i++) {
    for (let j = 0; j < length - 1 - i; j++) {
      if(arr[j]>arr[j+1]) {
        let temp = arr[j+1]
        arr[j+1] = arr[j]
        arr[j] = temp
      }
    }
  }
}
// mpSort(array)
// console.log(array)


function selectSort(arr) {
  const length = arr.length
  for (let i = 0; i < length - 1; i++) {
    let min = arr[i]
    let minIndex = i  
    for (let j = i+1; j < length; j++) {
      // const element = array[j];
      if(min>arr[j]) {
        minIndex = j
        min = arr[j]
      }
    }
    console.log(min, minIndex)
    let temp = arr[i]
    arr[i] = min
    arr[minIndex] = temp
  }
}
selectSort(array)
console.log(array)

// let array = [3,2,23,33,32,31,51,62,33,37,21,10,0]
function insertSort(arr) {
  const length = arr.length
  for (let i = 1; i < length; i++) {
    let temp = arr[i]
    // let j = i
    // let current = i
    for (let j = i; j>0 ; j--) {
      console.log(temp, arr[j-1])
      if(arr[j-1]>temp){
        arr[j] = arr[j-1]
      } else {
        arr[j] = temp
      }
    }
    // while(j>0) {
    //   if(arr[j-1] > temp) {
    //     arr[j] = arr[j-1]
    //   } else {
    //     break
    //   }
    //   j--
    // }
    // arr[j] = temp
  }
}
//[3,5,38,44]  [15]
// 3, 5, 15, 38, 44
// function insertSort(arr) {
//   let length = arr.length
//   for (let index = 1; index <length; index++) {
//     const temp = arr[index] //8 0 1
//     let j = index //1 2 3
//     while(j>0) {
//       if(arr[j-1]>temp) {
//         arr[j] = arr[j-1]
//       } else {
//         break
//       }
//       j--
//     }
//     arr[j] = temp
//   }
// }
// insertSort(array)
// console.log(array)

//快排 [3,2,3,1,2,3,4,5] => [...[2,3,1,2,3]  ,3, ...[4,5]]
//leftArr: [1,2] 2 rightArr: [3,3]
//leftArr:[] 1 rightArr: [2]
// [1,2], 2 , [3] 3 []
//1,2,2,3,4 3, 
function quickSort(arr) {
  if(arr.length <= 1) return arr
  const baseNum = arr[0]
  const leftArr = []
  const rightArr = []
  for (let i = 1; i < arr.length; i++) {
    if(arr[i]<=baseNum){leftArr.push(arr[i])}
    if(arr[i]>baseNum) {rightArr.push(arr[i])}
  }
  return [...quickSort(leftArr), baseNum, ...quickSort(rightArr)]
}
// console.log(quickSort(array))

//[6,3,6,3,3,2] => [6,3,6] [3,3,2]

//[6] [3,6]   // [3] [3,2]

// [6] [3],[6]

//[6]  [3], [6]
// [6], [3,6]
function mergeSort(arr) {
  if(arr.length === 1) return arr
  const middleIndex = Math.floor(arr.length/2)
  let leftArr = arr.slice(0 , middleIndex)
  let rightArr = arr.slice(middleIndex, arr.length)
  let leftResult = mergeSort(leftArr) //[3]
  let rightResult = mergeSort(rightArr) //[6]
  let result = []//[]   []  =>  [] [] => [2,3,3,3,6,6 ]
  while(leftResult.length || rightResult.length) {
    if(leftResult.length>0 && rightResult.length>0) {
     result.push(leftResult[0]>rightResult[0]?rightResult.shift():leftResult.shift())
    } else if(leftResult.length>0) {
      result.push(leftResult.shift())
    } else if(rightResult.length>0) {
      result.push(rightResult.shift())
    }
  }
  return result
}
// console.log(mergeSort(array))


class Dictionary{
  constructor() {
    this.value = {}
    this.length = 0
  }
  set(key, value) {
    this.value[key] = value
    this.length += 1
  }
}